HashMap

Un HashMap en Java est une structure de données qui implémente l'interface Map<K, V>. Il permet de stocker des paires clé-valeur et d’accéder rapidement aux valeurs à partir de leurs clés.

Avantages du HashMap

1. Accès rapide : Grâce au hachage, l’accès aux éléments est en O(1) en moyenne
2. Pas d'ordre imposé : un HashMap ne trie pas les clés, ce qui permet d’économiser du temps et de la mémoire.
3. Clés uniques : Il garantit que chaque clé est unique, ce qui est utile pour représenter des relations d’association.
4. Flexibilité : Accepte null comme clé et valeur.
5. Évolutivité : Automatiquement redimensionné lorsque la capacité est dépassée.

Inconvénients du HashMap

1. Consommation mémoire élevée : Un HashMap utilise des buckets (tableaux liés) et des objets supplémentaires, ce qui peut entraîner une consommation de mémoire importante.
2. Pas thread-safe : Il n'est pas synchronisé. Si plusieurs threads y accèdent simultanément, on doit utiliser Collections.synchronizedMap() ou ConcurrentHashMap.
3. Performance dégradée en cas de mauvais hachage : Si la fonction de hachage produit trop de collisions, les performances chutent et peuvent atteindre O(n) dans le pire des cas.
4. Ordre non garanti : Les éléments ne sont pas stockés dans l'ordre d'insertion. Pour un ordre garanti, il faut utiliser LinkedHashMap.

Éléments les plus rapides dans un HashMap

• Opérations get() et put() sont rapides en moyenne grâce au hachage (O(1)).
• Opération containsKey() est également O(1) en moyenne, car elle utilise la même logique que get().
• Supprimer une clé remove(key) est également optimisé (O(1) en moyenne).

Quand utiliser un HashMap ?

• Quand on a besoin d’un accès rapide aux éléments à partir d’une clé unique.
• Pour stocker et récupérer rapidement des données comme une table de correspondance (ex: cache, annuaire, dictionnaire).
• Quand l'ordre des éléments n'a pas d'importance.
• Pour éviter les doublons de clé et stocker des relations clé-valeur efficacement.

Différences de performance entre HashMap et ArrayList

Opération	ArrayList	HashMap
Ajout (add ou put)	O(1) (amortie)	O(1) (amortie)
Accès par index (get(index))	O(1)	N/A
Accès par clé (get(key))	N/A	O(1) (moyenne)
Recherche (contains(value))	O(n)	O(1) (pour containsKey)
Suppression (remove(value))	O(n)	O(1) (moyenne)

---

Pourquoi dit-on que HashMap est rapide ?

1. Recherche rapide par clé (get(key))

   • Dans une ArrayList, pour retrouver un élément en fonction de sa valeur, il faut parcourir toute la liste → O(n).
   • Dans un HashMap, retrouver une valeur en fonction de sa clé est O(1) en moyenne, car il utilise une fonction de hachage pour accéder directement au bon emplacement.

2. Suppression rapide (remove(key))

   • Dans une ArrayList, supprimer un élément au milieu est coûteux O(n) car il faut décaler tous les éléments suivants.
   • Dans un HashMap, supprimer une clé est O(1) en moyenne car il suffit de supprimer l’entrée dans la table de hachage.

Quand utiliser ArrayList ou HashMap ?

• **Si tu as besoin d’un accès rapide par indice, utilise ArrayList.
• Si tu veux associer des clés à des valeurs et y accéder rapidement par clé, utilise HashMap.

principales méthodes de HashMap<K, V> en Java :

Méthode	Description
put(K key, V value)	Ajoute ou remplace une paire clé-valeur dans la HashMap.
get(Object key)	Retourne la valeur associée à key, ou null si la clé n'existe pas.
boolean containsKey(Object key)	Vérifie si la HashMap contient une clé spécifique.
boolean containsValue(Object value)	Vérifie si la HashMap contient une valeur spécifique.
remove(Object key)	Supprime une entrée basée sur la clé et retourne la valeur supprimée.
void clear()	Supprime toutes les entrées de la HashMap.
boolean isEmpty()	Vérifie si la HashMap est vide.
int size()	Retourne le nombre d'éléments dans la HashMap.
Set<K> keySet()	Retourne un Set contenant toutes les clés.
Collection<V> values()	Retourne une collection contenant toutes les valeurs.
Set<Map.Entry<K, V>> entrySet()	Retourne un Set de toutes les entrées (clé-valeur).